#ifndef HEAP_H
#define HEAP_H

#include <OrderedArray.h>
#include <Globals.h>
#include <Lockable.h>


#define HEAP_INDEX_SIZE   0x20000
#define HEAP_MAGIC        0x123890AB
#define HEAP_MIN_SIZE     0x70000

/**
  Size information for a hole/block.
**/
#define NBACKTRACE 12
typedef struct
{
  u32int magic;
  bool isHole;
  u32int size;
  u32int pid;
  u32int backtrace[NBACKTRACE];
} Header;

typedef struct
{
  u32int magic;
  Header *header;
} Footer;

/**
  Global function - for comparison & sorting in index.
**/
extern bool lessThan(Header *a, Header *b);

/**
  Implements a heap. The algorithm is based on dlmalloc and uses tagged
  areas and an index of free areas.
  Every free or allocated area (block) has a header and footer around it.
  The footer has a pointer to the header, with the header also containing
  size information.
**/
class Heap : public Lockable
{
public:

  Heap() {};

  /**
    Creates a new Heap, with start address start, initial size end-start, 
    and expanding up to a maximum address of max.
  **/
  Heap(u32int start, u32int end, u32int max, bool isKernel=false);
  
  ~Heap();
  
  /**
    Finds / creates a block for data of size size. If pageAlign, it creates
    a block starting on a page boundary.
  **/
  void *allocate(u32int size, bool pageAlign=false);
  
  /**
    Releases/deallocates a block, p, assigned with allocate().
  **/
  void free(void *p);
  
  /**
    Tries to detect buffer overruns by walking the heap and checking magic numbers.
  **/
  void checkIntegrity();
  
  /**
    Returns the current heap size. For analysis purposes.
  **/
  u32int getSize()
  {
    return endAddress-startAddress;
  }
  
private:

  /**
    Increases the size of the heap, by requesting pages to be allocated.
    Heap size increases from size to the nearest page boundary after newSize.
  **/
  void expand(u32int newSize);
  
  /**
    Decreases the size of the heap, by requesting pages to be deallocated.
    Heap size decreases from size to the nearest page boundary after newSize.
    Returns the new size (endAddress-startAddress) - not guaranteed to be the
    same as newSize.
  **/
  u32int contract(u32int newSize);
  
  s32int findSmallestHole(u32int size, bool pageAlign);

  /**
    The index table - lists all available holes.
  **/
  OrderedArray<Header *, HEAP_INDEX_SIZE> *index;
  
  /**
    The start of our allocated space. Includes index table.
  **/
  u32int startAddress;
  
  /**
    The end of our currently allocated space. May be expanded up to maxAddress.
  **/
  u32int endAddress;
  
  /**
    The maximum possible address our heap can be expanded to.
  **/
  u32int maxAddress;
  
  /**
    If any pages requested by us should be marked as supervisor-only.
  **/
  bool isKernel;
};

#endif
